package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.LinkedProblem;

/**
 * https://leetcode.com/problems/linked-list-cycle-ii/
 *
 * 标有"注意的"两个地方, 是因为为了代码简短, 为了fast.next.next补位空的循环条件好写搞出来的.
 * 相当于head之前还有个不存在的虚假头, 两指针从那个地方开始. 两个注意的地方, 相当于在循环外先走了一步.
 * <p>
 * 当然也可以采用 142_1那种, 把while循环要判断的东西, 移动一部分到循环内
 *
 * @author tzp
 * @since 2020/10/19
 */
public class LC142 implements LinkedProblem {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode slow = head, fast = head.next;//注意!!!
        while (fast != null && fast.next != null && slow != fast) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (slow != fast) return null;
        slow = head;
        fast = fast.next;//注意!!!
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n5;
        System.out.println(new LC142().detectCycle(n1).val);
    }
}
